TNotes.leetcode

Appearance

0018. 四数之和【中等】

0018. 四数之和【中等】 ​

1. 📝 题目描述 ​

给你一个由 n 个整数组成的数组 nums，和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案。

示例 1：

txt
输入：nums = [1, 0, -1, 0, -2, 2], target = 0
输出：[
  [-2, -1, 1, 2],
  [-2, 0, 0, 2],
  [-1, 0, 0, 1]
]

示例 2：

txt
输入：nums = [2, 2, 2, 2, 2], target = 8
输出：[[2, 2, 2, 2]]

提示：

  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

2. 🎯 s.1 - 排序 + 双重枚举 + 双指针 ​

c
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume
 * caller calls free().
 */
int compare(const void* a, const void* b) {
    return (*(int*)a > *(int*)b) - (*(int*)a < *(int*)b);
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize,
              int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), compare);

    int capacity = 16;
    int** ans = (int**)malloc(capacity * sizeof(int*));
    *returnColumnSizes = (int*)malloc(capacity * sizeof(int));
    *returnSize = 0;

    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1])
                continue;
            int left = j + 1, right = numsSize - 1;
            while (left < right) {
                // C 版本用 long long 防止四数相加溢出（数有效内容可达 -4 * 10^9
                // ~ 4 * 10^9）
                long long sum =
                    (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    if (*returnSize == capacity) {
                        capacity *= 2;
                        ans = (int**)realloc(ans, capacity * sizeof(int*));
                        *returnColumnSizes = (int*)realloc(
                            *returnColumnSizes, capacity * sizeof(int));
                    }
                    ans[*returnSize] = (int*)malloc(4 * sizeof(int));
                    ans[*returnSize][0] = nums[i];
                    ans[*returnSize][1] = nums[j];
                    ans[*returnSize][2] = nums[left];
                    ans[*returnSize][3] = nums[right];
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;
                    while (left < right && nums[left] == nums[left + 1])
                        left++;
                    while (left < right && nums[right] == nums[right - 1])
                        right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return ans;
}
js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  nums.sort((a, b) => a - b)
  const ans = []
  const n = nums.length

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue
      let left = j + 1
      let right = n - 1
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right]
        if (sum === target) {
          ans.push([nums[i], nums[j], nums[left], nums[right]])
          while (left < right && nums[left] === nums[left + 1]) left++
          while (left < right && nums[right] === nums[right - 1]) right--
          left++
          right--
        } else if (sum < target) {
          left++
        } else {
          right--
        }
      }
    }
  }
  return ans
}
py
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans = []
        n = len(nums)

        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                left, right = j + 1, n - 1
                while left < right:
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s == target:
                        ans.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1
        return ans
  • 时间复杂度：O(n3)，排序 O(nlog⁡n)，外两层枚举 O(n2)，内层双指针 O(n)，整体 O(n3) 主导
  • 空间复杂度：O(log⁡n)，排序递归栈空间（不计输出数组）

算法思路：

  • 先对数组升序排序，使相同元素相邻，便于去重
  • 外两层分别枚举第一个数 nums[i] 和第二个数 nums[j]，问题转化为在 j 右侧找两数之和等于 target - nums[i] - nums[j]
  • 内层用左右双指针收缩，四数之和小于目标则 left++，大于目标则 right--，等于则记录并跳过相邻重复元素

Discussions